package easy;

/**
 * @author admin
 * 169. 多数元素(时间复杂度要求O（n），用排序的话时间复杂度为O（logn）)
 * 解题思路：Boyer-Moore 投票算法,一开始定义两个变量，一个来保存结果，一个用来
 * 计数，对数组遍历，首先判断count是否为0，为0则将第一个元素置为结果candidate，
 * 否则判断当前元素与candidate是否相同，相同则将count加1，不同减1，直到数组遍
 * 历完，返回candidate
 */
public class LeeCode169 {

    public int majorityElement(int[] nums) {
        int candidate = 0;
        int count = 0;
        for (int num : nums) {
            if (count == 0){
                candidate = num;
            }
            count += (num == candidate) ? 1 : -1;

        }
        return candidate;
    }

    public static void main(String[] args) {
        System.out.println(new LeeCode169().majorityElement(new int[]{2,2,1,1,1,2,2}));
    }
}
